﻿
(function() {

    //error reasons
    var reasons = new Array();
    reasons[G_GEO_SUCCESS] = "Sucesso";
    reasons[G_GEO_BAD_REQUEST] = "Pedido inválido. A direcção não foi processada com sucessso.";
    reasons[G_GEO_SERVER_ERROR] = "O pedido de geocodificação não pode ser processado.\n - Motivo desconhecido, verifique o zoom do mapa.";
    reasons[G_GEO_MISSING_QUERY] = "Um ou mais critérios de pesquisa em falta. \n\n Verifique que os endereços estão ou as coordenadas geográficas correctamente preenchidos.";
    reasons[G_GEO_MISSING_ADDRESS] = "Endereço em falta: um ou mais critérios de pesquisa em falta. \n\n Verifique que os endereços estão ou as coordenadas geográficas correctamente preenchidos.";
    reasons[G_GEO_UNKNOWN_ADDRESS] = "Endereço desconhecido: um ou mais critérios de pesquisa em falta. \n\n Verifique que os endereços estão ou as coordenadas geográficas correctamente preenchidos.";
    reasons[G_GEO_UNAVAILABLE_ADDRESS] = "Impossível gerar uma rota.\n\nNão existe um rota possível para os pontos indicados ou a precisão dos dados da região é demasiado baixa.";
    reasons[G_GEO_BAD_KEY] = "Chave inválida: a chave da API éinválida ou não corresponde ao domínio para a qual foi criada.";
    reasons[G_GEO_TOO_MANY_QUERIES] = "Foram ultrapassados os limites de pedidos para 24 horas ou foram submetidos demasiados pedidos em simultâneo.";
    reasons[G_GEO_UNKNOWN_DIRECTIONS] = "Percursos desconhecidos: a aplicação não conseguiu processar os percursos entre os pontos definidos.";

    var tie; // singleton
    var gebMap;           // The map DOM object
    var directionsPanel;  // The driving directions DOM object
    var gebDirections;    // The driving directions returned from GMAP API
    var gebGeocoder;      // The geocoder for addresses
    var maxTieSize = 24;  // A limit on the size of the problem, mostly to save Google servers from undue load.
    var maxTieBF = 0;     // Max size for brute force, may seem conservative, but ma
    var maxTieDynamic = 15;     // Max size for brute force, may seem conservative, but many browsers have limitations on run-time.
    var maxSize = 24;     // Max number of waypoints in one Google driving directions request.
    var maxTripSentry = 2000000000; // Approx. 63 years., this long a route should not be reached...
    var avoidHighways = false; // Whether to avoid highways. False by default.
    var travelMode = G_TRAVEL_MODE_DRIVING; // or G_TRAVEL_MODE_WALKING
    var distIndex;
    var waypoints = new Array();
    var addresses = new Array();
    var addr = new Array();
    var wpActive = new Array();
    var addressRequests = 0;
    var wayStr;
    var distances;
    var durations;
    var dist;
    var dur;
    var visited;
    var currPath;
    var bestPath;
    var bestTrip;
    var nextSet;
    var numActive;
    var chunkNode;
    var cachedDirections = false;

    var onSolveCallback = function() { };
    var originalOnFatalErrorCallback = function(tie, errMsg) { alert("A solicitação falhou: \n\n" + errMsg); }
    var onFatalErrorCallback = originalOnFatalErrorCallback;
    var onFatalError = originalOnFatalErrorCallback;
    var doNotContinue = false;
    var onLoadListener = null;
    var onFatalErrorListener = null;

    function tieAntColonyK2() {
        var alfa = 1.0; // The importance of the previous trails
        var beta = 1.0; // The importance of the durations
        var rho = 0.1;  // The decay rate of the pheromone trails
        var asymptoteFactor = 0.9; // The sharpness of the reward as the solutions approach the best solution
        var pher = new Array();
        var nextPher = new Array();
        var prob = new Array();
        var numAnts = 10;
        var numWaves = 10;
        for (var i = 0; i < numActive; ++i) {
            pher[i] = new Array();
            nextPher[i] = new Array();
        }
        for (var i = 0; i < numActive; ++i) {
            for (var j = 0; j < numActive; ++j) {
                pher[i][j] = 1;
                nextPher[i][j] = 0.0;
            }
        }

        var lastNode = 0;
        var startNode = 0;
        var numSteps = numActive - 1;
        var numValidDests = numActive;
        for (var wave = 0; wave < numWaves; ++wave) {
            for (var ant = 0; ant < numAnts; ++ant) {
                var curr = startNode;
                var currDist = 0;
                for (var i = 0; i < numActive; ++i) {
                    visited[i] = false;
                }
                currPath[0] = curr;
                for (var step = 0; step < numSteps; ++step) {
                    visited[curr] = true;
                    var cumProb = 0.0;
                    for (var next = 1; next < numValidDests; ++next) {
                        if (!visited[next]) {
                            prob[next] = Math.pow(pher[curr][next], alfa) *
      	      Math.pow(dur[curr][next], 0.0 - beta);
                            cumProb += prob[next];
                        }
                    }
                    var guess = Math.random() * cumProb;
                    var nextI = -1;
                    for (var next = 1; next < numValidDests; ++next) {
                        if (!visited[next]) {
                            nextI = next;
                            guess -= prob[next];
                            if (guess < 0) {
                                nextI = next;
                                break;
                            }
                        }
                    }
                    currDist += dur[curr][nextI];
                    currPath[step + 1] = nextI;
                    curr = nextI;
                }
                currPath[numSteps + 1] = lastNode;
                currDist += dur[curr][lastNode];

                // k2-rewire:
                var lastStep = numActive;
                var changed = true;
                var i = 0;
                while (changed) {
                    changed = false;
                    for (; i < lastStep - 2 && !changed; ++i) {
                        var cost = dur[currPath[i + 1]][currPath[i + 2]];
                        var revCost = dur[currPath[i + 2]][currPath[i + 1]];
                        var iCost = dur[currPath[i]][currPath[i + 1]];
                        var tmp, nowCost, newCost;
                        for (var j = i + 2; j < lastStep && !changed; ++j) {
                            nowCost = cost + iCost + dur[currPath[j]][currPath[j + 1]];
                            newCost = revCost + dur[currPath[i]][currPath[j]] + dur[currPath[i + 1]][currPath[j + 1]];
                            if (nowCost > newCost) {
                                currDist += newCost - nowCost;
                                // Reverse the detached road segment.
                                for (var k = 0; k < Math.floor((j - i) / 2); ++k) {
                                    tmp = currPath[i + 1 + k];
                                    currPath[i + 1 + k] = currPath[j - k];
                                    currPath[j - k] = tmp;
                                }
                                changed = true;
                                --i;
                            }
                            cost += dur[currPath[j]][currPath[j + 1]];
                            revCost += dur[currPath[j + 1]][currPath[j]];
                        }
                    }
                }

                if (currDist < bestTrip) {
                    bestPath = currPath;
                    bestTrip = currDist;
                }
                for (var i = 0; i <= numSteps; ++i) {
                    nextPher[currPath[i]][currPath[i + 1]] += (bestTrip - asymptoteFactor * bestTrip) / (numAnts * (currDist - asymptoteFactor * bestTrip));
                }
            }
            for (var i = 0; i < numActive; ++i) {
                for (var j = 0; j < numActive; ++j) {
                    pher[i][j] = pher[i][j] * (1.0 - rho) + rho * nextPher[i][j];
                    nextPher[i][j] = 0.0;
                }
            }
        }
    }

    function tieBruteForce(currNode, currLen, currStep) {
        // Set mode parameters:
        var numSteps = numActive;
        var lastNode = 0;
        var numToVisit = numActive;

        // If this route is promising:
        if (currLen + dur[currNode][lastNode] < bestTrip) {

            // If this is the last node:
            if (currStep == numSteps) {
                currLen += dur[currNode][lastNode];
                currPath[currStep] = lastNode;
                bestTrip = currLen;
                for (var i = 0; i <= numSteps; ++i) {
                    bestPath[i] = currPath[i];
                }
            } else {

                // Try all possible routes:
                for (var i = 1; i < numToVisit; ++i) {
                    if (!visited[i]) {
                        visited[i] = true;
                        currPath[currStep] = i;
                        tieBruteForce(i, currLen + dur[currNode][i], currStep + 1);
                        visited[i] = false;
                    }
                }
            }
        }
    }

    /* Finds the next integer that has num bits set to 1.
    */
    function nextSetOf(num) {
        var count = 0;
        var ret = 0;
        for (var i = 0; i < numActive; ++i) {
            count += nextSet[i];
        }
        if (count < num) {
            for (var i = 0; i < num; ++i) {
                nextSet[i] = 1;
            }
            for (var i = num; i < numActive; ++i) {
                nextSet[i] = 0;
            }
        } else {
            // Find first 1
            var firstOne = -1;
            for (var i = 0; i < numActive; ++i) {
                if (nextSet[i]) {
                    firstOne = i;
                    break;
                }
            }
            // Find first 0 greater than firstOne
            var firstZero = -1;
            for (var i = firstOne + 1; i < numActive; ++i) {
                if (!nextSet[i]) {
                    firstZero = i;
                    break;
                }
            }
            if (firstZero < 0) {
                return -1;
            }
            // Increment the first zero with ones behind it
            nextSet[firstZero] = 1;
            // Set the part behind that one to its lowest possible value
            for (var i = 0; i < firstZero - firstOne - 1; ++i) {
                nextSet[i] = 1;
            }
            for (var i = firstZero - firstOne - 1; i < firstZero; ++i) {
                nextSet[i] = 0;
            }
        }
        // Return the index for this set
        for (var i = 0; i < numActive; ++i) {
            ret += (nextSet[i] << i);
        }
        return ret;
    }

    function tieDynamic() {
        var numCombos = 1 << numActive;
        var C = new Array();
        var parent = new Array();
        for (var i = 0; i < numCombos; ++i) {
            C[i] = new Array();
            parent[i] = new Array();
            for (var j = 0; j < numActive; ++j) {
                C[i][j] = 0.0;
                parent[i][j] = 0;
            }
        }
        for (var k = 1; k < numActive; ++k) {
            var index = 1 + (1 << k);
            C[index][k] = dur[0][k];
        }
        for (var s = 3; s <= numActive; ++s) {
            for (var i = 0; i < numActive; ++i) {
                nextSet[i] = 0;
            }
            var index = nextSetOf(s);
            while (index >= 0) {
                for (var k = 1; k < numActive; ++k) {
                    if (nextSet[k]) {
                        var prevIndex = index - (1 << k);
                        C[index][k] = maxTripSentry;
                        for (var m = 1; m < numActive; ++m) {
                            if (nextSet[m] && m != k) {
                                if (C[prevIndex][m] + dur[m][k] < C[index][k]) {
                                    C[index][k] = C[prevIndex][m] + dur[m][k];
                                    parent[index][k] = m;
                                }
                            }
                        }
                    }
                }
                index = nextSetOf(s);
            }
        }
        for (var i = 0; i < numActive; ++i) {
            bestPath[i] = 0;
        }
        var index = (1 << numActive) - 1;

        var currNode = -1;
        bestPath[numActive] = 0;
        for (var i = 1; i < numActive; ++i) {
            if (C[index][i] + dur[i][0] < bestTrip) {
                bestTrip = C[index][i] + dur[i][0];
                currNode = i;
            }
        }
        bestPath[numActive - 1] = currNode;

        for (var i = numActive - 1; i > 0; --i) {
            currNode = parent[index][currNode];
            index -= (1 << bestPath[i]);
            bestPath[i - 1] = currNode;
        }
    }

    function makeLatLng(latLng) {
        if (String(latLng).substr(0, 1) == "(") {
            return (String(latLng).substr(1, String(latLng).length - 2));
        }
        else {
            return String(latLng);
        }

    }

    function getWayStr(curr) {
        var nextAbove = -1;
        for (var i = curr + 1; i < waypoints.length; ++i) {
            if (wpActive[i]) {
                if (nextAbove == -1) {
                    nextAbove = i;
                } else {
                    wayStr.push(makeLatLng(waypoints[i]));
                    wayStr.push(makeLatLng(waypoints[curr]));
                }
            }
        }
        if (nextAbove != -1) {
            wayStr.push(makeLatLng(waypoints[nextAbove]));
            getWayStr(nextAbove);
            wayStr.push(makeLatLng(waypoints[curr]));
        }
    }

    function getDistTable(curr, currInd) {
        var nextAbove = -1;
        var index = currInd;
        for (var i = curr + 1; i < waypoints.length; ++i) {
            if (wpActive[i]) {
                index++;
                if (nextAbove == -1) {
                    nextAbove = i;
                } else {
                    dist[currInd][index] = distances[distIndex];
                    dur[currInd][index] = durations[distIndex++];
                    dist[index][currInd] = distances[distIndex];
                    dur[index][currInd] = durations[distIndex++];
                }
            }
        }
        if (nextAbove != -1) {
            dist[currInd][currInd + 1] = distances[distIndex];
            dur[currInd][currInd + 1] = durations[distIndex++];
            getDistTable(nextAbove, currInd + 1);
            dist[currInd + 1][currInd] = distances[distIndex];
            dur[currInd + 1][currInd] = durations[distIndex++];
        }
    }

    function directions() {

        if (cachedDirections) {
            doTie(0);
        }

        wayStr = new Array();
        numActive = 0;
        for (var i = 0; i < waypoints.length; ++i) {
            if (wpActive[i]) ++numActive;
        }

        for (var i = 0; i < waypoints.length; ++i) {
            if (wpActive[i]) {
                wayStr.push(makeLatLng(waypoints[i]));
                getWayStr(i);
                break;
            }
        }

        // Roundtrip
        if (numActive > maxTieSize) {
            alert("Existem muitas localizações! Existem" + numActive + ", mas o limite é " + maxTieSize);
        } else {
            distances = new Array();
            durations = new Array();
            chunkNode = 0;
            nextChunk();
        }
    }

    function nextChunk() {

        if (chunkNode < wayStr.length) {

            var wayStrChunk = new Array();
            for (var i = 0; i < maxSize && i + chunkNode < wayStr.length; ++i) {
                wayStrChunk.push(wayStr[chunkNode + i]);
            }

            chunkNode += maxSize;
            if (chunkNode < wayStr.length - 1) {
                chunkNode--;
            }

            var myGebDirections = new GDirections(gebMap, directionsPanel);

            GEvent.addListener(myGebDirections, "error", function() {
                var errorMsg = reasons[myGebDirections.getStatus().code] +
                              "(Estado: " + myGebDirections.getStatus().code + ")";

                if (typeof errorMsg == 'undefined') errorMsg = 'Unknown error.';

                doNotContinue = true;
                onFatalError(tie, errorMsg);
            });

            GEvent.addListener(myGebDirections, "load", function() {
                // Save distances and durations
                for (var i = 0; i < myGebDirections.getNumRoutes(); ++i) {
                    durations.push(myGebDirections.getRoute(i).getDuration().seconds);
                    distances.push(myGebDirections.getRoute(i).getDistance().meters);
                }
                nextChunk();
            });

            GEvent.addListener(myGebDirections, "addoverlay", function() {
                // Remove the standard google maps icons:
                gebMap.clearOverlays();
                directionsPanel.innerHTML = "";
            });

            myGebDirections.loadFromWaypoints(wayStrChunk, { getSteps: false, getPolyline: false, preserveViewport: true, avoidHighways: avoidHighways, travelMode: travelMode });

        } else {
            readyTie();
        }
    }

    function readyTie() {
        // Get distances and durations into 2-d arrays:
        distIndex = 0;
        dist = new Array();
        dur = new Array();
        numActive = 0;

        for (var i = 0; i < waypoints.length; ++i) {
            if (wpActive[i]) {
                dist.push(new Array());
                dur.push(new Array());
                addr[numActive] = addresses[i];
                numActive++;
            }
        }

        for (var i = 0; i < numActive; ++i) {
            dist[i][i] = 0;
            dur[i][i] = 0;
        }

        for (var i = 0; i < waypoints.length; ++i) {
            if (wpActive[i]) {
                getDistTable(i, 0);
                break;
            }
        }

        doTie();
    }


    function doTie() {
        // Calculate shortest roundtrip:
        visited = new Array();
        for (var i = 0; i < numActive; ++i) {
            visited[i] = false;
        }
        currPath = new Array();
        bestPath = new Array();
        nextSet = new Array();
        bestTrip = maxTripSentry;
        visited[0] = true;
        currPath[0] = 0;
        cachedDirections = true;
        if (numActive <= maxTieBF) {
            tieBruteForce(0, 0, 1);
        } else if (numActive <= maxTieDynamic) {
            tieDynamic();
        } else {
            tieAntColonyK2();
        }

        wayStrChunk = new Array();
        var wpIndices = new Array();
        for (var i = 0; i < waypoints.length; ++i) {
            if (wpActive[i]) {
                wpIndices.push(i);
            }
        }
        var bestPathLatLngStr = "";
        for (var i = 0; i < bestPath.length; ++i) {
            wayStrChunk.push(makeLatLng(waypoints[wpIndices[bestPath[i]]]));
            bestPathLatLngStr += makeLatLng(waypoints[wpIndices[bestPath[i]]]) + "\n";
        }
        if (typeof onSolveCallback == 'function') {
            if (onLoadListener)
                GEvent.removeListener(onLoadListener);

            onLoadListener = GEvent.addListener(gebDirections, 'addoverlay', function() {
                onSolveCallback(tie);
            });
        }

        if (onFatalErrorListener)
            GEvent.removeListener(onFatalErrorListener);
        onFatalErrorListener = GEvent.addListener(gebDirections, 'error', onFatalErrorCallback)

        gebDirections.loadFromWaypoints(wayStrChunk, { getSteps: true, getPolyline: true, preserveViewport: false, avoidHighways: avoidHighways, travelMode: travelMode });
    }


    function addWaypoint(latLng) {
        var freeInd = -1;
        for (var i = 0; i < waypoints.length; ++i) {
            if (!wpActive[i]) {
                freeInd = i;
                break;
            }
        }
        if (freeInd == -1) {
            if (waypoints.length < maxTieSize) {
                waypoints.push(latLng);
                wpActive.push(true);
                freeInd = waypoints.length - 1;
            } else {
                return (-1);
            }
        } else {
            waypoints[freeInd] = latLng;
            wpActive[freeInd] = true;
        }
        return (freeInd);
    }


    function addAddress(address, callback) {
        addressRequests++;
        gebGeocoder.getLatLng(address, function(latLng) {
            addressRequests--;
            if (!latLng) {
                if (typeof (callback) == 'function')
                    callback(address);
            } else {
                var freeInd = addWaypoint(latLng);
                addresses[freeInd] = address;
                if (typeof callback == 'function')
                    callback(address, latLng);
            }
        });
    }


    TieRouteSolver.prototype.startOver = function() {
        waypoints = new Array();
        addresses = new Array();
        addr = new Array();
        wpActive = new Array();
        wayStr = "";
        distances = new Array();
        durations = new Array();
        dist = new Array();
        dur = new Array();
        visited = new Array();
        currPath = new Array();
        bestPath = new Array();
        bestTrip = new Array();
        nextSet = new Array();
        numActive = 0;
        chunkNode = 0;
        addressRequests = 0;
        cachedDirections = false;
        onSolveCallback = function() { };
        doNotContinue = false;
    }


    function TieRouteSolver(map, panel, onFatalError) {
        if (tie) {
            alert('You can only create one TieRouteSolver at a time.');
            return;
        }

        gebMap = map;
        directionsPanel = panel;

        gebGeocoder = new GClientGeocoder();
        gebDirections = new GDirections(gebMap, directionsPanel);
        onFatalErrorCallback = onFatalError; // only for errors fatal errors, not geocoding errors
        tie = this;
    }


    TieRouteSolver.prototype.addAddress = function(address, callback) {
        if (!this.isReady()) {
            setTimeout(function() { tie.addAddress(address, callback) }, 20);
            return;
        }
        addAddress(address, callback);
    };

    TieRouteSolver.prototype.makeLatLng = function(latlng) {
        return makeLatLng(latlng);
    };

    TieRouteSolver.prototype.addWaypoint = function(latLng) {
        addWaypoint(latLng);
    };

    TieRouteSolver.prototype.getWaypoints = function() {
        var wp = [];
        for (var i = 0; i < waypoints.length; i++) {
            if (wpActive[i])
                wp.push(waypoints[i]);
        }
        return wp;
    };

    TieRouteSolver.prototype.getAddresses = function() {
        var addrs = [];
        for (var i = 0; i < addresses.length; i++) {
            if (wpActive[i])
                addrs.push(addresses[i]);
        }
        return addrs;
    };

    TieRouteSolver.prototype.removeWaypoint = function(latLng) {
        for (var i = 0; i < waypoints.length; ++i) {
            if (wpActive[i] && waypoints[i].equals(latLng)) {
                wpActive[i] = false;
                return true;
            }
        }
        return false;
    };

    TieRouteSolver.prototype.removeAddress = function(addr) {
        for (var i = 0; i < addresses.length; ++i) {
            if (wpActive[i] && addresses[i] == addr) {
                wpActive[i] = false;
                return true;
            }
        }
        return false;
    };

    TieRouteSolver.prototype.getGDirections = function() {
        return gebDirections;
    };

    // Returns the order that the input locations was visited in.
    //   getOrder()[0] is always the starting location.
    //   getOrder()[1] gives the first location visited, getOrder()[2]
    //   gives the second location visited and so on.
    TieRouteSolver.prototype.getOrder = function() {
        return bestPath;
    }

    // Methods affecting the way driving directions are computed
    TieRouteSolver.prototype.getAvoidHighways = function() {
        return avoidHighways;
    }

    TieRouteSolver.prototype.setAvoidHighways = function(avoid) {
        avoidHighways = avoid;
    }

    TieRouteSolver.prototype.getTravelMode = function() {
        return travelMode;
    }

    TieRouteSolver.prototype.setTravelMode = function(travelM) {
        travelMode = travelM;
    }

    TieRouteSolver.prototype.getDurations = function() {
        return dur;
    }

    // we assume that we have enough waypoints
    TieRouteSolver.prototype.isReady = function() {
        return addressRequests == 0;
    };

    TieRouteSolver.prototype.solveRoundTrip = function(callback) {
        if (doNotContinue) {
            alert('Cannot continue after fatal errors.');
            return;
        }

        if (!this.isReady()) {
            setTimeout(function() { tie.solveRoundTrip(callback) }, 20);
            return;
        }
        if (typeof callback == 'function')
            onSolveCallback = callback;

        directions();
    };

    window.TieRouteSolver = TieRouteSolver;

})();
